import java.util.*;
import java.io.*;

public class Automaton {

    private String pattern;     //patron recherche
    private char[] alphabet;    // alphabet des genomes
	private int[][] fct;
	
    public Automaton(String pattern, char[] alphabet)
    {
        this.alphabet = alphabet;
        this.pattern = pattern;
        /*
Initialiser δ à 0 
for q = 0 : m 
 	for chaque caractère a dans ΣP 
 		k = min(m+1, q+2) 
 		do 
 			k = k - 1 
 		while k>0 et ( (Pk ⊃Pqa) est faux) 
 		δ(q, a) = k 
 	end for 
end for


         */
        
        int m=pattern.length();
        int k=0;
        String temp = "";
        this.fct = new int[m][alphabet.length];
        
        for (int q=0;q<m;q++)
        {
      	  for (int p=0;p<alphabet.length;p++)
      	  {
      		  temp+=alphabet[p];
      		  k = (m+1 < q+2) ? m+1 : q+2;
      		  do
      		  {
      			 k--; 
      		  }
      		  while(k>0 && !(temp.endsWith(pattern.substring(0,k))));
      			  
      		  this.fct[q][p] = k;
      		  temp=temp.substring(0,q);
      	  }
      	  int max=0;
      	  int index=0;
      	  for(int i=0; i<this.fct[q].length; i++){
      		  if(this.fct[q][i] >max){
      			  max = this.fct[q][i];
      			  index=i;
      		  }
      	  }
      	  temp+=alphabet[index];
        	
        }
        

        
    }
    
    int match(String seq){
    	int nbr = 0;
    	int q=0;

	for(int i=1; i<seq.length(); i++){
    	   char lettre = seq.charAt(i);
    	   int counter=0;
    	   for(counter=0; counter<this.alphabet.length; counter++){
    		   if (lettre == alphabet[counter]){
    			   break;
    		   }   
    	   }  
	    	   q=this.fct[q][counter];
	    			   
	    		if(q==pattern.length()){

	    			int shift = i-pattern.length();
	    			System.out.println("Pattern occurs with shift" + shift);

	    			nbr++;
	    			q=0;
	    			counter=0;
	    		}
    		
       }
    	return nbr;
     }
    
}
